Available today are computer programs known as "computerized mapping programs." Those programs can display digital maps, often complete with detailed road networks down to the city-street level. Typically, a user can input a location and the mapping program will display a map on-screen of the selected location. The mapping program generally displays several features of the map, such as countries, states, counties, cities, hospitals, churches, and the like. For the purpose of this discussion, each feature which can be displayed on the map is termed an "object."
Each object on the display will typically have a label identifying what the object is. For instance, the city Atlanta will appear on the map as a point object with the label "Atlanta" positioned near the point. For the purpose of this discussion, a "point" is an object on the map which is represented by a discrete point symbol, such as a city. In contrast are "area" objects, such as countries or states, and "line" objects, such as rivers.
Each type of object can be labeled slightly differently, based on cartographic standards in use in the mapping industry. Each type of object has several available label positions of varying cartographic preference. For instance, the label position to the northeast of a point symbol is the cartographically preferred label position for a point. If that position is not available, then other label positions can be chosen, such as the southeast position, the northwest position, or the southwest position, in descending order of cartographic preference.
Areas also have label positions of descending cartographic preference. For instance, the most cartographically preferred area label position is in the center of the area. Other positions are also available for an area label, such as above the center of the area or below the center of the area. Also, the label size and character spacing can be reduced to help place the label. Likewise, line objects are preferably labeled with a straight line label, positioned somewhere collinear with the line.
Existing mapping programs have various systems for labeling the objects which are displayed on a map. For instance, a typical mapping program in use today simply places labels in a pre-determined position near the object. Changing the display does not affect the label position. Such a system is considered a static system. Static systems suffer from many problems. For instance, modern mapping programs allow the user to request a particular object to be displayed and labeled, such as the user's residence or office. In that situation, the mapping program displays the ordinary map features, such as cities and states, as well as the user's requested object with a label. The object which the user requests is displayed regardless of what objects it may collide with. The term "collide" means that two objects on a map attempt to collocate in the same location on a display of the map.
Accordingly, the user's requested object can collide with an existing map feature. Avoiding collision is a premium concern in computerized mapping programs. In a static system, there is no way to relocate a pre-determined label to another position. As a result, often the user's requested object will prevent displaying either an existing object, or the label for that object. A system which can display as many objects with their respective labels as possible is desirable.
Also, most mapping programs today allow a user to "zoom" in and out, meaning that the scale factor can be changed. At each scale, different objects may be visible. For instance, at one scale factor, a hospital may be visible, while panning out makes the hospital insignificant with respect to the other objects which are displayed, such as cities or counties. Accordingly, a system which can relocate labels for objects in response to collisions between objects at different scales is desirable.
Two related systems which can relocate labels for objects, termed "dynamic systems," make use of a system "score" or a "temperature." In those systems, the location of each of the objects and labels which can be displayed is determined. The score relates to the total number of collisions between labels and objects to be displayed as well as the number of objects which are not in cartographically preferred positions. The systems attempt to minimize the score of the display by relocating each label to a new position and testing the new score of the system after the move. If the move makes the score better, than the move is kept. If a temperature system is used, a move which actually makes the score worse may be kept in a small number of cases. After all objects have been examined in a single pass, the temperature is reduced, which has the effect of making it harder to accept bad moves. The temperature system, where some bad moves are accepted, is called "Simulated Annealing." A system which uses a score but not a temperature, which only accepts good moves, is called a "Gradient Descent."
In those systems, the number of collisions is first determined and stored in memory. Then, a random relocation is made of a label for an object, and the number of collisions is again determined. If the number of collisions decreases, then the label is left in the new position. If the number of collisions increases, then a random number function combined with the temperature, if applicable, are used to determine if the new position is kept. As the temperature decreases, the probability of keeping such a move decreases. The system then moves a second label to a new position. Again the number of collisions is determined, and the new label position is either maintained or rejected, based on the same criteria. The system repeats this process for every label. Once all labels have been visited, the temperature is reduced and the algorithm begins again with the first object to be labeled. The system repeats this process as many times as necessary to minimize the system score below a pre-determined threshold or until a minimum reduction in score is achieved in a pass through all the objects. Often, a single object label will be relocated several times before the minimum score is achieved. A severe problem with these types of systems is the time cost of performing a sufficient number of computations to achieve acceptable results. Because of the random nature of the testing, the computational time makes the Gradient Descent and Simulated Annealing systems undesirable for applications desiring robust performance.
Another system is used in mapping programs which attempt to locate labels in such a manner as to avoid colliding with currently displayed objects. For instance, some mapping programs employ a "greedy algorithm," which seeks to place a label corresponding to an object in a given label position. If a collision occurs between the label and an object which has already been displayed, and which has been identified as desirable, the label will be relocated to any label position which is not already occupied. While the greedy algorithm system improves computational time, this system suffers from several problems as well. For instance, greedy algorithm systems do not anticipate the location of objects yet to be displayed when placing a label for an object. In other words, a greedy algorithm system places a label in the first available label position which is not already occupied by an existing object or label. A system which seeks to avoid currently displayed objects, as well as objects which remain to be displayed, is desirable.
A system and method for labeling objects on a computerized map in an efficient manner, while avoiding collisions with both more important objects and lesser important objects has eluded those skilled in the art. There is a need for a system which can quickly label objects while avoiding currently displayed objects, as well as objects which remain to be displayed.